/*
 * Name: 王旭东
 * StudentID: 2014302580343
 * Date: 2015/10/9
 * Locale: ISSWHU, Wuhan Hubei
 * Email: xukiro[AT]outlook.com
 */
#include <iostream>
using namespace std;

struct Node {
    int coeff;  /* Coefficient */
    int exp;    /* Exponent */
    Node *next; /* Next node */
    Node(int c = 0, int e = 0) {
        coeff = c;
        exp = e;
        next = NULL;
    }
};

class Polynomial {
private:
    /* Dummy node, head->coeff serve as reference counter */
    Node *head;
private:
    Node *takeFirst(void);
public:
    /* Default constructor */
    Polynomial() { head = new Node(1); };
    /* Shallow copy constructor */
    Polynomial(const Polynomial &poly) {
        ++(head = poly.head)->coeff;
    };
    ~Polynomial();

    void removeAll(void);
    void insertTerm(Node *term);
    void inputPoly (const char *prompt);
    void outputPoly(const char *prompt);
    void addPoly(const Polynomial &operand, int k = 1);

    inline const Polynomial &operator= (const Polynomial &poly);
    Polynomial operator+ (const Polynomial &operand);
    Polynomial operator- (const Polynomial &operand);
    Polynomial operator* (const Polynomial &operand);
};

/* Destructor wil delete the whole link only if
 * after decreasing, the reference counter == 0 */
Polynomial::~Polynomial()
{
    if (--head->coeff == 0) {
        removeAll();
        delete(head);
    }
}

/* Add some terms by inputing coefficient and exponent */
void Polynomial::inputPoly(const char *prompt)
{
    int c, e;
    cout << prompt << " := ";
    while (cin >> c) {
        if (c == 0)
            break;
        cin >> e;
        insertTerm(new Node(c, e));
    }
}

/* Print the Polynomial in human-readable way */
void Polynomial::outputPoly(const char *prompt)
{
    Node *p = head->next;
    cout << prompt << "\t= ";
    if (p == NULL) {
        cout << "0" << endl;
        return;
    }
    for (;;) {
        cout << "(" << p->coeff << " * x^" << p->exp << ")";
        if ((p = p->next) == NULL) {
            cout << endl;
            return;
        }
        cout << " + ";
    }
}

/* Insert *term to polynomial, *term won't be duplicated */
void Polynomial::insertTerm(Node *t)
{
    /* p => (the position t to be inserted) => p->next => ... */
    Node *p = head;
    if (t->coeff == 0) {
        /* Ensure the coefficient of new term is non-zero */
        delete(t);
        return;
    }
    while (p->next != NULL) {
        if (p->next->exp == t->exp) {
            if ((p->next->coeff += t->coeff) == 0) {
                /* The coefficient of a term is non-zero */
                Node *savedptr = p->next->next;
                delete(p->next);
                p->next = savedptr;
            }
            delete(t);
            return;
        }
        if (p->next->exp < t->exp)
            break;
        p = p->next;
    }
    t->next = p->next;
    p->next = t;
}


/* Delete all notes except the head */
void Polynomial::removeAll(void)
{
    Node *p;
    while ((p = takeFirst()) != NULL)
        delete(p);
}

/* Return the first node, which will be removed from the link */
Node *Polynomial::takeFirst(void)
{
    if (head->next == NULL)
        return NULL;
    Node *term = head->next;
    head->next = term->next;
    return term;
}

/* Perform `this = this + k * operand' */
void Polynomial::addPoly(const Polynomial &operand, int k)
{
    Node *p = operand.head;
    while ((p = p->next) != NULL)
        insertTerm(new Node(k * p->coeff, p->exp));
}

const Polynomial &Polynomial::operator= (const Polynomial &poly)
{
    this->~Polynomial();
    ++(head = poly.head)->coeff;
    return *this;
}

Polynomial Polynomial::operator+ (const Polynomial &operand)
{
    Polynomial sum;
    sum.addPoly(*this);
    sum.addPoly(operand);
    return sum;
}

Polynomial Polynomial::operator- (const Polynomial &operand)
{
    Polynomial diff;
    diff.addPoly(*this);
    diff.addPoly(operand, -1);
    return diff;
}

Polynomial Polynomial::operator* (const Polynomial &operand)
{
    Polynomial product;
    Node *lterm = head;
    while ((lterm = lterm->next) != NULL){
        Node *rterm = operand.head;
        while ((rterm = rterm->next) != NULL) {
            int c = lterm->coeff * rterm->coeff;
            int e = lterm->exp   + rterm->exp;
            product.insertTerm(new Node(c, e));
        }
    }
    return product;
}

int main(int argc, char *argv[])
{
    Polynomial a, b, sum, diff, product;

    cout << "Note: Input a polynomial by enter its coefficient and "
        << "exponent in pairs of each term. End with coefficient '0'.\n"
        << "For example, `A := 3 -2   9 2   -4 0  1 3   0' represents"
        << " A = (3 / x^2) + (9 * x^2) - 4 + (x^3)\n" << endl;
    a.inputPoly("A");      //input polynomial a
    a.outputPoly("A");
    b.inputPoly("B");      //input polynomial b
    b.outputPoly("B");

    diff    = a - b;
    sum     = a + b;
    product = a * b;

    sum.outputPoly("SUM");
    diff.outputPoly("DIFF");
    product.outputPoly("PRODUCT");

    return 0;
}

